/**
 * 描述：前缀树，通过Java中的TreeMap来实现
 *
 * @author 王博
 * @version 1.0
 * create 2018-10-24-11:30
 */
import java.util.TreeMap;//使用Java内置的TreeMap
public class Trie{//不使用泛型，默认是Character。

    private class Node{

        public boolean isWord;//用来判断当我们访问到这个节点的时候，是否已经找到了一个单词
        public TreeMap<Character,Node> next;//从当前节点到下一个节点的映射

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap <> ();
        }

        public Node(){
            this(false);//如果不传入，默认是false
        }
    }

    private Node root;
    private int size;//存储的单词的个数

    public Trie(){
        root = new Node ();
        size = 0 ;
    }

    public int getSize( ) {
        return size;
    }

    /**
     * 添加一个字符串进trie
     * @param word 需要添加的新单词 .非递归写法。
     */
    public void add(String word){

        Node cur = root;
        for ( int i = 0 ; i <word.length ()  ; i++ ) {
            char c = word.charAt (i);
            if(cur.next.get (c)==null)//cur这个节点的下一个没有指向C的节点
                cur.next.put (c,new Node ());
            cur = cur.next.get (c); //cur还是一个Node类型。
        }

        if(!cur.isWord){
            //说明之前没有这个单词来过。
            cur.isWord = true;
            size++;
        }
    }

    public boolean contains(String word){
        Node cur = root;
        for ( int i = 0 ; i < word.length () ; i++ ) {
            char c = word.charAt (i);
            if(cur.next.get (c)==null)//不包括这个映射。
                return false;
            cur = cur.next.get (c);
        }
        return cur.isWord;

    }
}
